class Node{
    constructor(element){
        this.left = null;
        this.right = null;
        this.element = element;
    }
}

class Tree{
    constructor(){
        this.root = null; //记录根节点
        this.prevArr = [];//前序遍历的值
        this.postArr = []; //后序遍历的值
    }

    //插入节点
    insert(element){
        let node = new Node(element)
        //1.树是否有节点
        if(this.root === null){
            this.root = node;
        }else{
            //比父节点小的放左边，比父节点大的放右侧
            this.insertNode(node,this.root)
        }
    }

    insertNode(newNode,rootNode){
        if(newNode.element < rootNode.element){
            //左边
            if(rootNode.left === null){
                rootNode.left = newNode
            }else{
                this.insertNode(newNode,rootNode.left);
            }
        }else{
            //右边
            if(rootNode.right === null){
                rootNode.right = newNode
            }else{
                this.insertNode(newNode,rootNode.right);
            }
        }
    }

    min(){
        return this.minNode(this.root)//最小值
    }

    minNode(rootNode){
        while(rootNode.left != null){
            rootNode = rootNode.left;
        }
        return rootNode
    }

    max(){
        return this.maxNode(this.root)//最小值
    }

    maxNode(rootNode){
        while(rootNode.right != null){
            rootNode = rootNode.right;
        }
        return rootNode
    }

    search(element){  //true false
        return this.searchNode(element,this.root)//true false
    }

    searchNode(element,node){
        //1当前的树是否为空
        if(node === null){
            return false
        }

        if(element > node.element){
            //右边
            return this.searchNode(element,node.right);
        }else if(element < node.element){
            //左边
            return this.searchNode(element,node.left);
        }else{
            return true
        }
    }

    //中序遍历  先序遍历  后序遍历
    inOrderTraverse(){
        this.inOrderTraverseNode(this.root);
    }

    inOrderTraverseNode(node){
        if(node != null){
            this.inOrderTraverseNode(node.left);
            console.log(node.element);
            this.inOrderTraverseNode(node.right);
        }
    }

    preOrderTraverse(){
        console.log("34567890")
        this.preOrderTraverseNode(this.root);
    }

    preOrderTraverseNode(node){
        if(node != null){
            // console.log("=====",this.prevArr)
            console.log(node.element);
            this.prevArr.push(node.element);
            this.preOrderTraverseNode(node.left);
            this.preOrderTraverseNode(node.right);
        }
    }

    postOrderTraverse(){
        this.postOrderTraverseNode(this.root);
    }

    postOrderTraverseNode(node){
        if(node != null){
            this.postOrderTraverseNode(node.left);
            this.postOrderTraverseNode(node.right);
            // console.log(node.element);
            this.postArr.push(node.element);
        }
    }

    //删除
    remove(element){
        this.root = this.removeNode(element,this.root);
    }

    removeNode(element,node){
        //1.判断当前节点是否为空
        if(node === null){
            return null;
        }

        
        if(element > node.element){
            //2.1比父节点大  右侧
            //右边
            node.right = this.removeNode(element,node.right);//5.right = null
            
            return node
        }else if(element < node.element){
            //2.2比父节点小  左侧
            node.left = this.removeNode(element,node.left);
            return node
        }else{
            
            //2.3 相等
            //2.3.1 无子节点

            if(node.left === null && node.right === null){ //6节点
                return null;
            }
            
            //2.3.2 只有一个子节点
            if(node.left === null){
                //没有左侧子节点，有右侧子节点
                return node.right
            }else if(node.right === null){
                //没有右侧子节点，有左侧子节点
                return node.left
            }

            //2.3.3 有两个子节点
            //找最小值
            let endNode = this.minNode(node.right);
            //把最小值给到node
            node.element = endNode.element;

            node.right = this.removeNode(node.element,node.right)

            console.log(endNode);
            return node
        }
    }

    //查找树的深度

    maxDepth(){
        return this.depth(this.root) //最大的深度
    }

    depth(node){
        if(node === null){
            return 0
        }

        let leftDepth = this.depth(node.left);
        let rightDepth = this.depth(node.right);

        let num = leftDepth > rightDepth ? leftDepth : rightDepth;

        return num+1
    }

}

let tree = new Tree();

tree.insert(11);

tree.insert(7);

tree.insert(5);

tree.insert(3);

tree.insert(6);

tree.insert(15);

tree.insert(13);

tree.insert(20);

tree.insert(18);

tree.insert(25);

// console.log(tree.remove(15));

// console.log(tree.remove(6));

// console.log(tree.remove(5));

// console.log(tree);
// console.log(tree.maxDepth());

tree.preOrderTraverse();

console.log(tree.prevArr)

function bubbleSort(arr=[]){
    let {length} = arr;
    
    for(let i = 0;i<length-1;i++){
        for(let j = 0;j<length-1-i;j++){
            if(arr[j] > arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]]  //借助数组的解构，交换值
            }
        }
    }
    return arr
}

console.log(bubbleSort(tree.prevArr))


function selectSort(arr=[]){
    let {length} =arr;

    // let init = 0;

    let min; //初始的位置

    for(let i = 0;i<length-1;i++){
        min = i;
        for(let j = i;j<length;j++){
            if(arr[min] > arr[j]){
                min = j;
            }
        }
        if(i != min){
            [arr[min],arr[i]] = [arr[i],arr[min]]
        }
    }
    return arr //排完序的数组
}